ArrayDeque = ArrayDeque or {}

function ArrayDeque.new()
    local inst = {
        __cname = "lang.ArrayDeque"
    }

    local arr = {}
    local head = 1
    local tail = 1
    local itr = nil

    function inst:count()
        return tail - head
    end

    local function getForLoopTail()
        return tail - 1
    end

    function inst:clear()
        if head ~= tail then
            for i=head,getForLoopTail() do
                arr[i] = nil
            end
        end
        head = 1
        tail = 1
        end

    function inst:contains(v)
        if head == tail then return false end
        for i=head,getForLoopTail() do
            if v == arr[i] then
                return true
            end
        end
        return false
    end

    function inst:addFirst(v)
        if head == tail then
            self:addLast(v)
        else
            if 1 == head then
                for i=getForLoopTail(),head,-1 do --后移1个位置
                    arr[i+1] = arr[i]
                end
                arr[1] = v
                tail = tail + 1
            else
                head = head - 1
                arr[head] = v
            end
        end
    end

    function inst:addLast(v)
        arr[tail] = v
        tail = tail + 1
    end

    function inst:peekFirst()
        if head == tail then return nil end
        return arr[head]
    end

    function inst:peekLast()
        if head == tail then return nil end
        return arr[tail - 1]
    end

    function inst:removeFirst()
        if head == tail then return nil end
        local first = arr[head]
        arr[head] = nil
        head = head + 1

        if head == tail then
            head = 1
            tail = 1
        else
            local forLoopTail = getForLoopTail()
            --2个元素, 前面空了1个(50%); 100个元素, 前面空了50个(50%); 仅仅超过50%就移动不够完善
            if head > 8 and head / forLoopTail >= 0.5 then
                local j = 1
                for i=head,forLoopTail do
                    arr[j] = arr[i]
                    j = j + 1
                end
                for i=j,forLoopTail do
                    arr[j] = nil
                end
                tail = tail - head + 1
                head = 1
                --print(string.format("move: head:%s, tail:%s", head, tail))
            end
        end
        return first
    end

    function inst:removeLast()
        if head == tail then return nil end
        local last = arr[tail]
        arr[tail] = nil
        tail = tail - 1
        return last
    end

    function inst:getEnumerator()
        if nil == itr then
            itr = {
                _head = 0,
                _cur = nil,
            }

            function itr:getCurrent()
                return self._cur
            end

            function itr:moveNext()
                if self._head == tail then return false end
                self._cur = arr[self._head]
                self._head = self._head + 1
                return true
            end
        end
        itr._head = head
        itr._cur = nil
        return itr
    end

    function inst:__tostring()
        if head == tail then return "" end
        local strTb = {}
        for i= head,getForLoopTail() do
            local item = arr[i]
			table.insert(strTb, (nil == item) and "nil" or tostring(item))
        end
        return table.concat(strTb, ",")
    end

    function inst:__len()
        return self:count()
    end

    function inst:__index(k)
        error("ArrayDeque: invalid member: " .. k)
    end

    function inst:__newindex(k, v)
        error("ArrayDeque: add member error: " .. k)
    end

    setmetatable(inst, inst)
    return inst
end

function ArrayDeque.__call()
    return ArrayDeque.new()
end
setmetatable(ArrayDeque, ArrayDeque)


local function Test1()
    local dq = ArrayDeque()

    assert(false == dq:contains("one"), "contains error")
    assert(nil == dq:peekFirst(), "peekFirst error")
    assert(nil == dq:peekLast(), "peekLast error")
    assert(0 == dq:count(), "count error")

    dq:addFirst("one")
    assert("one" == dq:peekFirst(), "addFirst error")
    assert("one" == dq:peekLast(), "addFirst error")
    assert(1 == dq:count(), "addFirst error")
    assert(dq:contains("one"), "addFirst error")

    dq:addLast("two")
    assert("one" == dq:peekFirst(), "addLast error")
    assert("two" == dq:peekLast(), "addLast error")
    assert(2 == dq:count(), "addLast error")
    assert(dq:contains("two"), "addLast error")

    dq:addFirst("zero")
    assert("zero" == dq:peekFirst(), "addFirst error")
    assert("two" == dq:peekLast(), "addFirst error")
    assert(3 == dq:count(), "addFirst error")
    assert(dq:contains("zero"), "addFirst error")

    assert(false == dq:contains("three"), "contains error")

    dq:removeFirst()
    assert("one" == dq:peekFirst(), "removeFirst error")
    assert("two" == dq:peekLast(), "removeFirst error")
    assert(2 == dq:count(), "removeFirst error")
    assert(false == dq:contains("zero"), "removeFirst error")

    dq:removeFirst()
    assert("two" == dq:peekFirst(), "removeFirst error")
    assert("two" == dq:peekLast(), "removeFirst error")
    assert(1 == dq:count(), "removeFirst error")
    assert(false == dq:contains("one"), "removeFirst error")

    dq:addFirst("one")
    assert("one" == dq:peekFirst(), "removeFirst error")
    assert("two" == dq:peekLast(), "removeFirst error")
    assert(2 == dq:count(), "addFirst error")
    assert(false == dq:contains("zero"), "removeFirst error")

    dq:removeFirst()
    dq:removeFirst()
    assert(nil == dq:peekFirst(), "removeFirst error")
    assert(nil == dq:peekLast(), "removeFirst error")
    assert(0 == dq:count(), "removeFirst error")
    assert(false == dq:contains("two"), "removeFirst error")

    dq:addLast("zero")
    dq:addLast("one")
    dq:addLast("two")
    dq:removeFirst()
    dq:removeLast()
    assert("one" == dq:peekFirst(), "removeLast error")
    assert("one" == dq:peekLast(), "removeLast error")
    assert(1 == dq:count(), "removeLast error")
    assert(false == dq:contains("zero"), "removeLast error")

    dq:addLast("two")
    dq:addLast("three")
    local itr = dq:getEnumerator()
    while (itr:moveNext()) do
        print(itr:getCurrent())
    end
end

--Test1()

local function TestRemoveFirst()
    local dq = ArrayDeque()

    for i=1,20 do
        dq:addLast(i)
        assert(i == dq:count())
    end

    for i=20,3,-1 do
        dq:removeFirst()
        assert((i-1) == dq:count())
    end
    assert(19 == dq:peekFirst())
    assert(20 == dq:peekLast())

    dq:removeFirst()
    dq:removeFirst()
    assert(0 == dq:count())

    assert(nil == dq:removeFirst())
end

TestRemoveFirst()